/*
 * Diseno de Algoritmos 2
 * Abril Julio 2011
 * David Subero
 * Daniel Bruzual
 * Job Shop resuelto a traves de un algoritmo genetico
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <unistd.h>
#include <sys/time.h>

#include "Lista.h"
#include "genetic.h"

//tamano de la poblacion
int tam_pob;

//numero de generaciones
int num_gen;

//probabilidad de crossover
float p_cruce;

//probabilidad de mutacion
float p_muta;

//numero de cromosomas nuevos por generacion
int k_new;

//numero de trabajos
int nro_t;

//numero de maquinas
int nro_m; 

//numero de operaciones totales 
int nro_op;

/* arreglo que contiene todas las operaciones
 * ordenadas por trabajo, y por precedencia
 * dentro de ese trabajo.
*/
operacion *operaciones;


void seed () {
    struct timeval t;
    gettimeofday(&t,NULL);
    srand(t.tv_sec * t.tv_usec);
}


/* Modelo de Algoritmo genetico estacionario
 * Seleccion por ruleta
 * Tamano de poblacion constante
 *
 */
int genetic_algorithm(int hibrido){
  poblacion* pobla, *selec, *hijos;
  cromosoma * mejor, *mejor_local;
  int i = 1;
  seed();

  //inicializar poblacion
  ini_poblacion(&pobla, tam_pob);

  //calcular costos de los individuos y
  mejor = update_makespans(pobla);  
  if(mejor == NULL) return -1;

  //por numero de generaciones
  while(i != num_gen){

    //seleccionar individuos
    selec =  seleccionar_ruleta(pobla, k_new);
    if (selec == NULL) return -1;
    
    //cruzar con probabilidad
    hijos = reproducir(selec, p_cruce, hibrido);
    if(hijos == NULL) return -1;

    //mutar con probabilidad
    mutar(hijos, p_muta);
 
    //hallar costos y guardar mejor
    if(pobla->tam > 0){
      mejor_local = update_makespans(pobla);
      if(mejor_local == NULL) return -1;
      
      if(mejor_local->makespan < mejor->makespan){
	free(mejor->genes);
	free(mejor);
	mejor = mejor_local;
      }
    }
   
    //reemplazar de la poblacion original
    reemplazo(pobla, hijos);

    i++;
  }
  
  printf("antes: %d\n", mejor->makespan);


  operacion *** res_mejorado = cromosoma_a_schedule(mejor);

  int new_cost = local_search(res_mejorado);

  //  print_matriz(res_mejorado);

  cromosoma * convertido = schedule_a_cromosoma(res_mejorado);
  //  convertido->makespan = new_cost;

  set_makespan(convertido);
  printf("despues: %d\n", convertido->makespan);
  //  pretty_print(res_mejorado);

  return 1;
}


/* Inicializa y almacena la poblacion inicial aleatoria, de tamano pop_size*/
int ini_poblacion(poblacion** p, int pop_size){
  int i, j, a, pos;
  int por_asignar[nro_t];
 
  if((*p = (poblacion *)malloc(sizeof(poblacion))) == NULL){
    return -1;
  }
  
  if(((*p)->pobla = (cromosoma *)calloc(pop_size, sizeof(cromosoma))) == NULL){
    return -1;
  }
  for(i=0; i<pop_size; i++) {

    if(((*p)->pobla[i].genes = (int *) calloc(nro_op, sizeof(int))) == NULL){
      return -1;
    }
  
    for(j=0; j<nro_t; por_asignar[j++] = nro_m);
    pos = 0;
    
    while(pos<nro_op){
      do {
	a = rand() % nro_t;
      } while(por_asignar[a] == 0);
      
      (*p)->pobla[i].genes[pos++] = a;
      //      printf("%d\n", pos);
      por_asignar[a]--;
      
      }
  }
  (*p)->tam = pop_size;
  return 0;
}



/* Dado un cromosoma, calcula y almacena el tiempo
 * que tarda en ejecutarse la planificacion que representa
 */
int set_makespan(cromosoma* xy){
  int voy_trab[nro_t], mk_trab[nro_t], mk_maq[nro_m];
  int i, op_id, job, mk_op, max = 0;
  operacion* op; 
  
  for(i=0; i<nro_t; i++){
    voy_trab[i] = 0;
    mk_trab[i] = 0;
  }
  for(i=0; i<nro_m; i++){
    mk_maq[i] = 0;
  }

  for(i=0; i<nro_op; i++){
    job = xy->genes[i];
    op_id = job*nro_m + voy_trab[job];
    op = &operaciones[op_id];

    voy_trab[job]++;

    mk_op = MAX(mk_trab[job], mk_maq[op->maquina]) + op->costo;

    mk_trab[job] = mk_op;
    mk_maq[op->maquina] = mk_op;
  }

  for(i=0; i<nro_m; i++){
    max = MAX(max, mk_maq[i]);
  }
  xy->makespan = max;
  return max;
}

/*
 * Cruza dos cromosomas y produce un hijo. Se genera un string
 * aleatorio de 0s y 1s que representa de que padre se deben
 * tomar los genes.
 */
cromosoma *cruzarPPX(cromosoma *p0, cromosoma *p1) {
  cromosoma *hijo;
  int i, j, genes[2][nro_op], pos[2];
  int padre_escogido, otro_padre;
  
  if ((hijo = (cromosoma *) malloc(sizeof(cromosoma))) == NULL) {
    return NULL;
  }
  if ((hijo->genes = (int *) calloc(nro_op, sizeof(int))) == NULL){
    return NULL;
  }
  for (i=0; i<nro_op; i++) {
    genes[0][i] = p0->genes[i];
    genes[1][i] = p1->genes[i];
  }
  
  pos[0] = pos[1] = 0;
  for (i=0; i<nro_op; i++) {
    padre_escogido = rand() % 2;
    otro_padre = (padre_escogido + 1) % 2;
    
    //se busca el nuevo gen
    while (genes[padre_escogido][pos[padre_escogido]] == -1) {
      pos[padre_escogido]++;
    }
    hijo->genes[i] = genes[padre_escogido][pos[padre_escogido]++];
    
    //se tacha el gen en el otro padre
    for (j=pos[otro_padre]; j<nro_op; j++) {
     if (genes[otro_padre][j] == hijo->genes[i]) {
       genes[otro_padre][j] = -1;
       break;
     }
    }
 }
  
  //se calcula makespan del hijo
  set_makespan(hijo);
  return hijo;
}

/*
 * Calcula el costo de todos los cromosomas de una poblacion.
 * Devuelve el de mejor costo.
 */
cromosoma * update_makespans(poblacion * p){
  int i, lim = p->tam, min = 0, cost, first = 1;
  cromosoma * best, *res;
  for(i = 0; i< lim; i++){
    cost = set_makespan(&(p->pobla[i]));
    if(cost<min || first){
      min = cost;
      best = &(p->pobla[i]);
      first = 0;
    }

  }
  res = (cromosoma *) malloc(sizeof(cromosoma));
  if(res == NULL) return NULL;

  res->genes = (int *) calloc(nro_op, sizeof(int));
  if(res->genes == NULL) return NULL;

  for(i=0;i<nro_op; res->genes[i]=best->genes[i++]);
  res->makespan = min;

  return res;
}

/* Selecciona tam_sel individuos de la poblacion pop.
 * Se le asigna un rango de probabilidad a cada individuo
 * en funcion a su costo. Luego se hace ruleta para escoger
 * los individuos seleccionados.
 */
poblacion * seleccionar_ruleta(poblacion* pop, int tam_sel){
  int  proba[pop->tam], i, lim_i, lim_d, s;
  int pos_libre = 0;
  float  sum = 0, acum[pop->tam], val;
  poblacion * new;

  if((new = (poblacion *) malloc(sizeof(poblacion))) == NULL){
    return NULL;
  }

  if((new->pobla = (cromosoma *) calloc(tam_sel, sizeof(cromosoma))) == NULL){
    return NULL;
  }

  if(tam_sel <= 0){
    new->tam = 0;
    return new;
  }

  for(i=0; i<pop->tam; i++){
    sum += 1.0/  pop->pobla[i].makespan ;
    acum[i] = sum;
  }

  for(i=0; i<tam_sel; i++){
    val = (rand() / (RAND_MAX * 1.0))*sum;

    //busqueda binaria para saber cual fue el elegido
    lim_i = 0;
    lim_d = pop->tam - 1;
  
    while(lim_i < lim_d){
      
      s = (lim_d + lim_i) / 2;
      if(val < acum[s]){
	lim_d = s;
      } else if (val > acum[s]){
	lim_i = s+1;
      } else if (val = acum[s]){
	lim_i = s;
	break;
      }
    }
    
    //agregar a la poblacion
    new->pobla[pos_libre++] = pop->pobla[lim_i];
  }

  new->tam = pos_libre ;
  return new;

}


/* Dada la poblacion pop, hace cruces con probabilidad
 * hasta generar sus hijos */
poblacion * reproducir(poblacion * pop, float prob_cruce, int hibrido){
  int i, pos_libre = 0;
  float coin;
  cromosoma *tmp;
  poblacion * res = (poblacion *)malloc(sizeof(poblacion));
  
  if(prob_cruce == 0 || pop->tam == 0) return pop;

  if(res==NULL) return NULL;

  res->pobla = calloc(pop->tam, sizeof(cromosoma));
  if(res->pobla==NULL) return NULL;

  for(i=0; i<pop->tam-1; i++){
    coin = rand() / (RAND_MAX*1.0);

    if(coin < prob_cruce){
      tmp = cruzarPPX(&(pop->pobla[i]), &(pop->pobla[i+1]));
      res->pobla[pos_libre++] = *tmp;
      free(tmp);
    }
  }
  /* res->pobla = realloc(res->pobla, sizeof(cromosoma)*pos_libre);
     if(res->pobla == NULL) return NULL;*/
 
  res->tam = pos_libre;

  operacion *** temp;
  cromosoma * temp2;
  for(i=0; i<res->tam; i++){
    temp = cromosoma_a_schedule(&(res->pobla[i]));
	if (hibrido) local_search(temp);
    temp2 = schedule_a_cromosoma(temp);
    res->pobla[i] = *temp2;
  }


  return res;
  
}

/*
 * Muta una ploblacion haciendo intercambios (swaps) de genes. Cada
 * cromosoma puede ser mutado una sola vez, con probabilidad prob_mutar.
 *
 */
void mutar(poblacion * sanos, float prob_mutar){
  int i, pos1, pos2, tmp;
  float coin;

  for(i=0; i<sanos->tam; i++){
    coin = rand()/RAND_MAX;
    if(coin < prob_mutar){
      pos1 = rand()%nro_op;
      pos2 = rand()%nro_op;

      tmp = sanos->pobla[i].genes[pos1];
      sanos->pobla[i].genes[pos1] = sanos->pobla[i].genes[pos2];
      sanos->pobla[i].genes[pos2] = tmp;
    }
  }
}

/*
 * Reemplaza los peores individuos de la poblacion "grande" por 
 * los individuos de la poblacion "peq". El tamano de la poblacion
 * se mantiene constante.
 */
void reemplazo(poblacion * grande, poblacion * peq){
  int pos_peores = 0, pos = 0, i, c;
  int peores[peq->tam];

  if(peq->tam <= 0) return;

   //buscar los peores de "grande" 
  for(i=0; i<peq->tam; i++){
    peores[i] = i;
  }
  
  for(;i<grande->tam; i++){
    pos = 0;
    do {
      if(grande->pobla[i].makespan > grande->pobla[peores[pos]].makespan){
	peores[pos] = i;
	break;
      }
      pos++;
    } while (pos != peq->tam);
  }

  //reemplazo
  for(i=0; i<peq->tam; i++){
    //free(grande->pobla[peores[i]].genes);
    grande->pobla[peores[i]] = peq->pobla[i];
  }

  //borro los peq, pues ya forman parte de la poblacion
  //free(peq);
}

/*
 * Convierte una planificacion representada como una matriz, 
 * donde las filas son maquinas y las columnas son el orden
 * de las operaciones en esas maquinas, a un cromosoma.
 */
cromosoma * schedule_a_cromosoma(operacion*** in){
  int asignadas[nro_op], i, pre_trab, pos_maq[nro_m], pos_gen = 0;
  operacion * op;
  cromosoma * res = (cromosoma *) malloc(sizeof(cromosoma));
  if(res == NULL) return NULL;
  res->genes = (int *) calloc(nro_op, sizeof(int));
  if(res->genes == NULL) return NULL;

  for(i=0; i<nro_m; i++){
    pos_maq[i] = 0;
  }

  for(i=0; i<nro_op; i++){
    asignadas[i] = 0;
  }

  int m = 0;
  i = 0;
  while(i < nro_op){
    if(pos_maq[m] < nro_t){
      op = in[m][pos_maq[m]];
      
      //si es primera operacion de un trabajo
      //puede ser agregada al orden
      if(op->id % nro_m == 0 || asignadas[op->id - 1]){
	res->genes[pos_gen] =  op->id / nro_m;
	
	asignadas[op->id] = 1;
	pos_gen++;
	pos_maq[m]++;
	i++;
      }
    }
    m = (m+1) % nro_m;
  }
  
  set_makespan(res);
  return res;
}

/* Convierte un cromosoma en una planificacion representada como una
 * matriz donde las filas son las maquinas y las columnas son las operaciones
 * que se ejecutan en esas maquinas en orden.
 */
operacion *** cromosoma_a_schedule(cromosoma* in){
  int i, asignadas[nro_t], pos_libre[nro_m], op_number, op_id, job_id, pos_maq;
  operacion * op, *pre =NULL;
  operacion *** res = calloc(nro_m, sizeof(operacion**));

  if(res == NULL) return NULL;

  for(i=0; i<nro_m; i++){
    res[i] = calloc(nro_t, sizeof(operacion*));
    if(res[i] == NULL) return NULL;
  }

  for(i=0; i<nro_t; i++){
    asignadas[i] = 0;
  }
  for(i=0; i<nro_m; i++){
    pos_libre[i] = 0;
  }


  for(i=0; i<nro_op; i++){
    job_id = in->genes[i];
    op_number = asignadas[job_id];
    op_id = job_id*nro_m + op_number;
    op = &(operaciones[op_id]);
    pos_maq = pos_libre[op->maquina];
    res[op->maquina][pos_maq] = op;

    if(pos_maq == 0){
      op->pm = NULL;
    } else {
      op->pm = res[op->maquina][pos_maq - 1];
      res[op->maquina][pos_maq - 1]->sm = op;
      if(pos_maq == nro_t - 1){
	op->sm = NULL;
      }
    }
    
    asignadas[job_id]++;
    pos_libre[op->maquina]++;
    
  }

  return res;
}


void pretty_print(operacion*** sol){
  int i, j;

  for(i=0; i<nro_m; i++){
    for(j=0; j<nro_t; j++){
      printf("(%d, %d)  ",sol[i][j]->id/nro_m, sol[i][j]->id%nro_m);
    }
    printf("\n");
  }
  
}

void print_matriz(operacion*** sol){
  int i, j;

  for(i=0; i<nro_m; i++){
    for(j=0; j<nro_t; j++){
      if(j != nro_t -1 && j!=0){
	printf("(%d, %d, %d)  ", sol[i][j]->pm->id, sol[i][j]->id, sol[i][j]->sm->id);
      } else if (j ==nro_t -1){
	printf("(%d, %d, NULL) \n", sol[i][j]->pm->id, sol[i][j]->id);
      } else if (j ==0){
	printf("(NULL, %d, %d)  ",   sol[i][j]->id, sol[i][j]->sm->id);
      }
    }

  }
}



int main (int argc, char **argv) {
  int error, option, hibrido = 0;
  extern char *optarg;
  extern int optopt;
  char *archivo_instancia = NULL;
  

  while ((option = getopt(argc,argv,":n:c:m:i:f:k:h")) != -1) {
    switch (option) {
    case 'n':
      tam_pob = atoi(optarg);
      break;
    case 'f':
      archivo_instancia = optarg;
      break;
    case 'm':
      p_muta = atof(optarg);
      break;
    case 'c':
      p_cruce = atof(optarg);
      break;
    case 'i':
      num_gen = atoi(optarg);
      break;
    case 'k':
      k_new = atoi(optarg);
      break;
    case 'h':
      hibrido = 1;
      break;
    case ':':
      printf("ERROR: a la opcion -%c le falta su argumento\n",optopt);
      exit(1);
    case '?':
      printf("ERROR: parametro desconocido %c\n",optopt);
      exit(1);
      
    }
  }
  
  if (!archivo_instancia) {
    printf("Debe especificar un archivo de caso de prueba.\nUse el flag -f <archivo>\n");
    error = 1;
  }
  
  if(tam_pob <2){
    printf("El tamano de la poblacion debe ser mayor a 2 (flag -n).\n");
    error = 1;
  }

  if(num_gen < 1){
    printf("Debe haber al menos una generacion (flag -i).\n");
    error = 1;    
  }

  if(p_cruce < 0 || p_cruce > 1){
    printf("La probabilidad de cruce debe estar entre 0 y 1 (flag -c).\n");
    error = 1;
  }

  if(p_muta <0 || p_muta >1){
    printf("La probabilidad de mutacion debe estar entre 0 y 1 (flag -m).\n");
    error = 1;
    
  }
  if(error == 1) exit(1);

  if (error = leer_instancia(archivo_instancia)) {
    if (error == -1) printf("ERROR: la memoria disponible no es suficiente\n");
  	exit(1);
  }


  genetic_algorithm(hibrido);
 
  return 0;
}


/* Lee el archivo de una instancia e inicializa todas las estructuras
 * Parametros:
 *		archivo: nombre del archivo de la instancia
 * Valor de retorno:
 *		1 si el archivo no existe o si el formato del archivo no es valido
 *		-1 si no hay suficiente memoria disponible
 *		0 en otro caso
 */
int leer_instancia (char *archivo) {
  int i, j, maquina, costo;
  operacion *predecesor;
  FILE *fp;
  if ((fp = fopen(archivo, "r")) == NULL) {
    printf("ERROR: no se encontro el archivo \"%s\"\n",archivo);
    return 1;
  }

  if(!fscanf(fp, "%d %d\n", &nro_t, &nro_m)) {
    printf("ERROR: formato invalido\n");
    return 1;
  }
	
  //todas los trabajos tienen una operacion por maquina
  nro_op = nro_t * nro_m; 

  operaciones = (operacion *) calloc(nro_op,sizeof(operacion));
  if (operaciones == NULL) return -1;

	
  for (i=0; i<nro_t; i++) {
    predecesor = NULL;
    for (j=0; j<nro_m; j++) {
      if(!fscanf(fp, "%d %d\n", &maquina, &costo)) {
	printf("ERROR: formato invalido\n");
	return 1;
      }
      operaciones[i*nro_m + j].id = i*nro_m + j;
      operaciones[i*nro_m + j].costo = costo;
      operaciones[i*nro_m + j].maquina = maquina;
      operaciones[i*nro_m + j].pj = predecesor;
      operaciones[i*nro_m + j].pm = operaciones[i*nro_m + j].sm = NULL;
      if (j < nro_m - 1) {
	operaciones[i*nro_m + j].sj = operaciones + i*nro_m + j + 1;
      } else {
	operaciones[i*nro_m + j].sj = NULL;
      }
      
      predecesor = operaciones + i*nro_m + j;
    }
  }
  fclose(fp);
  return 0;
}



//LOCAL SEARCH

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/* Calcula los nodos que estan en el camino critico y
 * guarda el id de cada uno en un arreglo llamado nodos
 * Parametros:
 *		nodos: arreglo que contiene los id de las operaciones que se encuentran
 *			   en el camino critico
 *		solucion: matriz que representa el orden de operaciones en las maquinas
 *              posiciones: hash que dado un id de operacion, dice la ubicacion en el
 *                          schedule
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		cantidad de operaciones del camino critico
 */
int camino_critico(int ** nodos, operacion *** solucion, int *posiciones, int costo_sol, int r_sol[], int t_sol[]){
  int i, id, tama;
  operacion* op,* sm,* sj, *sig;
  Lista camino;
  inicializa(&camino);
  
  //buscar la primera operacion de alguna maquina
  //que sea parte de un camino critico
  for(i=0; i<nro_m; i++){
    op = solucion[i][0];
    if(op->costo + t_sol[op->id] == costo_sol){
      //es el primer nodo de un camino critico
      push(op->id, &camino);
      sig = op;
      break;
    }
  }

 //recorrer el grafo buscando UN camino critico
 while(1){
   if (posiciones[sig->id] % nro_t < nro_t - 1) {
     sm = solucion[posiciones[sig->id] / nro_t][posiciones[sig->id] % nro_t + 1];
   } else {
     sm = NULL;
   }
   sj = sig->sj;
   if(sm != NULL && r_sol[sm->id] + sm->costo + t_sol[sm->id] == costo_sol
      && r_sol[sm->id] - sig->costo == r_sol[sig->id]){
     //el sucesor en la maquina forma parte del camino critico
     push(sm->id, &camino);
     sig = sm;
   } else if(sj != NULL){
     //si el sucesor en la maquina no esta en el camino critico
     //entonces el sucesor en trabajo si lo esta
     push(sj->id, &camino);
     sig = sj;
   } else {
     break;
   }
 }
  
  //Copiar el resultado a un arreglo
  tama = tam(&camino);
  *nodos = (int *) calloc(tama, sizeof(int));

  for(i=0; i<tama; i++){
    (*nodos)[i] = desencolar(&camino);
  }
  return tama;
}

/*
 * Calcula el earliest starting time de la operacion op segun la planificacion que 
 * representa (operacion *** solucion).
 * Como el calculo es recursivo, se guardan los valores ya calculados en operaciones_est
 * de tal manera a no volverlos a calcular.
 */
int calcular_r (operacion ***solucion, int *posiciones, int operaciones_est[], operacion *op) {
  int est, eft_pj = -1, eft_pm = -1;
  operacion *pm;
  if (!operaciones_est[op->id]) {
    if (posiciones[op->id] % nro_t > 0) {
      pm = solucion[posiciones[op->id] / nro_t][posiciones[op->id] % nro_t - 1];
      eft_pm = calcular_r(solucion,posiciones,operaciones_est,pm) + pm->costo;
    }
    if (op->pj) {
      eft_pj = calcular_r(solucion,posiciones,operaciones_est,op->pj) + op->pj->costo;
    }

    est = operaciones_est[op->id] = MAX(eft_pj, eft_pm);

    if(est == -1){
      est = operaciones_est[op->id] = 0;
    }
  } else {
    est = operaciones_est[op->id];
  }
  return est;
}

/*
 * Calcula el tiempo mas tarde en que op puede comenzar, sin atrasar la planificacion
 * Como es recursivo el calculo, se guarda en colas[] los valores que ya han sido
 * calculados.
 */
int calcular_t(operacion ***solucion, int *posiciones, int colas[], operacion *op ){
  int est, est_sm = -1, est_sj = -1;
  operacion *sm;
  if(!colas[op->id]){
    if(posiciones[op->id] % nro_t < nro_t - 1){
	  sm = solucion[posiciones[op->id] / nro_t][posiciones[op->id] % nro_t + 1];
      est_sm = calcular_t(solucion,posiciones,colas, sm) + sm->costo;
    }
    if(op->sj){
      est_sj = calcular_t(solucion,posiciones,colas, op->sj) + op->sj->costo;
    }

    est = colas[op->id] = MAX(est_sm, est_sj);

    if(est == -1){
      est = colas[op->id] = 0;
    }
  } else {
    est = colas[op->id];
  }
  return est;
}

/*
 * Calcula el costo de una planificacion, siendo este el tiempo que tarda en completarse
 * todos los trabajos.
 * in:
 *    solucion        matriz que representa la planificacion. cada fila es una maquina
 *    posiciones      hash que indica dado una operacion, en que punto de la planificacion
 *                    se encuentra.
 *    operaciones_est tiempo mas temprano de comienzo de cada operacion.
 *    colas           tiempo mas tarde de comienzo (sin retrasar la planificacion).
 */
int costo_solucion (operacion ***solucion, int *posiciones, int *operaciones_est, int *colas) {
  int i, est, max;

  for (i=0; i<nro_op; i++) {
    operaciones_est[i] = 0;
    colas[i] = 0;
  }
  est = calcular_r(solucion,posiciones,operaciones_est,solucion[0][nro_t-1]);
  max = solucion[0][nro_t-1]->id;
  for (i=1; i<nro_m; i++) {
    est = calcular_r(solucion,posiciones,operaciones_est,solucion[i][nro_t-1]) +  solucion[i][nro_t-1]->costo;
    if (est > operaciones_est[max] + operaciones[max].costo) {
      max = solucion[i][nro_t-1]->id;
    }
  }	

  for(i=0; i<nro_m; i++){
    calcular_t(solucion,posiciones,colas, solucion[i][0]);
  }

  return operaciones_est[max] + operaciones[max].costo;
}



/* Ejecuta el movimiento de las operaciones que se encuentran en el orden
 * representado por el arreglo actual para que queden en el orden representado
 * por el arreglo movimiento
 * Parametros:
 *              solucion: matriz que representa la planificacion. las filas son maquinas.
 *              posiciones: hash que dado una operacion, da la ubicacion en la planific.
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el movimiento
 *		movimiento: arreglo que representa el orden de las operaciones
 *					despues de ejecutar el movimiento
 *		tam_movimiento: cantidad de operaciones involucradas en el movimiento
 */
void hacer_movimiento (operacion ***solucion, int *posiciones, operacion *actual[], operacion *movimiento[], int tam_movimiento) {
  int i, j, pos, pos2, maq, sit;
  operacion * op;
  pos2 =pos = posiciones[actual[0]->id];
  

  for (i=0; i<tam_movimiento; i++) {
   op = solucion[pos / nro_t][pos % nro_t]= movimiento[i];

   posiciones[movimiento[i]->id] = pos++;
  }

  maq = pos2/nro_t;
  sit = pos2%nro_t;

  for(i=0; i<tam_movimiento; i++){
    if(sit != 0){
      op = solucion[maq][sit]->pm = solucion[maq][sit -1];
      op->sm = solucion[maq][sit];

    } else {
      solucion[maq][sit]->pm = NULL;
    }
    if(sit != nro_t -1){
      op = solucion[maq][sit]->sm = solucion[maq][sit + 1];
      op->pm = solucion[maq][sit];
    } else {
      solucion[maq][sit]->sm = NULL;
    }
    sit++;
  }


}

/* Calcula el movimiento que se debe realizar para obtener el mejor vecino
 * segun la vecindad N1
 * Parametros:
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el mejor movimiento
 *		mejor: arreglo que representa el orden de las operaciones
 *			   despues de ejecutar el mejor movimiento
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		ultimos: arreglo de operaciones finales de cada maquina
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		-1 en caso de no encontrar algun vecino que no esta prohibido
 *		en otro caso, cantidad de operaciones involucradas en el mejor movimiento
 */
int mejor_movimiento_n1 (operacion ***solucion, int *posiciones, operacion *actual[], operacion *mejor[], operacion ** primeros, operacion ** ultimos, int costo_sol, int r_sol[], int t_sol[]) {
  int i, *cam_crit, tam_cam_crit, u, v;
  int mejor_cota, mejor_cota_aux, tam_movimiento, tam_movimiento_aux;
  operacion *actual_aux[3], *mejor_aux[3];

  int found = 0;
  tam_cam_crit = camino_critico(&cam_crit, solucion, posiciones, costo_sol, r_sol, t_sol);
	
  //busco un primer movimiento
    for (i=0; i<tam_cam_crit-1; i++) {
        if (operaciones[cam_crit[i]].maquina == operaciones[cam_crit[i+1]].maquina) {
            actual[0] = operaciones + cam_crit[i];
			actual[1] = operaciones + cam_crit[i+1];
			mejor[0] = operaciones + cam_crit[i+1];
			mejor[1] = operaciones + cam_crit[i];
			hacer_movimiento(solucion,posiciones,actual,mejor,2);
			mejor_cota = costo_solucion(solucion,posiciones, r_sol, t_sol);
			hacer_movimiento(solucion,posiciones,mejor,actual,2);
			u = cam_crit[i];
			v = cam_crit[i+1];
			i++;
			found = 1;
			break;
        }
    }
    //busco el mejor movimiento
    for (; i<tam_cam_crit-1; i++) {
      if (operaciones[cam_crit[i]].maquina == operaciones[cam_crit[i+1]].maquina) {
	actual_aux[0] = operaciones + cam_crit[i];
	actual_aux[1] = operaciones + cam_crit[i+1];
	mejor_aux[0] = operaciones + cam_crit[i+1];
	mejor_aux[1] = operaciones + cam_crit[i];
	hacer_movimiento(solucion,posiciones,actual_aux,mejor_aux,2);
	mejor_cota_aux = costo_solucion(solucion, posiciones, r_sol, t_sol);
	hacer_movimiento(solucion,posiciones,mejor_aux,actual_aux,2);
	if (mejor_cota_aux < mejor_cota) {
	  mejor_cota = mejor_cota_aux;
	  memcpy(actual, actual_aux, 2*sizeof(operacion *));
	  memcpy(mejor, mejor_aux, 2*sizeof(operacion *));
	      u = cam_crit[i];
	      v = cam_crit[i+1];
	}
      }
    }
  if(!found) return -1;
 
  free(cam_crit);

  return 2;
}

/* Busqueda local mejor-mejor sobre solucion.
 * Devuelve el costo de la mejor solucion encontrada.
 */
int local_search (operacion ***solucion) {
  int i, j, k, posiciones[nro_op], r_sol[nro_op], t_sol[nro_op], *cam_crit, tam_cam_crit;
  int costo_actual, costo_mejor, tam_movimiento;
  operacion* primeros[nro_m], *ultimos[nro_m], *actual[3], *movimiento[3], *mejor_solucion[nro_m][nro_t];

  for (i=0; i<nro_m; i++) {
	for (j=0; j<nro_t; j++) {
      posiciones[solucion[i][j]->id] = i*nro_t + j;
    }
  }

  costo_mejor = costo_actual = costo_solucion(solucion, posiciones, r_sol, t_sol);

  while (1) {
    for (i=0; i<nro_m; i++) {
      primeros[i] = solucion[i][0];
      ultimos[i] = solucion[i][nro_t-1];
    }
    tam_movimiento = mejor_movimiento_n1(solucion, posiciones, actual, movimiento, primeros, ultimos, costo_actual, r_sol,t_sol);

    if(tam_movimiento == -1){ //no hay mas vecinos
		printf("vecindad vacia\n");
      break;
    }

    hacer_movimiento(solucion,posiciones,actual,movimiento,tam_movimiento);

    costo_actual = costo_solucion(solucion, posiciones, r_sol, t_sol);

    if (costo_actual < costo_mejor) {
      costo_mejor = costo_actual;
      
      //Se guarda la mejor solucion
      for(j=0; j<nro_m; j++) {
        for (k=0; k<nro_t; k++) {
          mejor_solucion[j][k] = solucion[j][k];
        }
      }
    } else {//criterio de parada (no se encontro un mejor vecino)
      break;
    }
  }

  return costo_mejor;
}
//LOCAL SEARCH
